`
https://leetcode.cn/problems/substring-with-concatenation-of-all-words/
`

/**
 * @param {string} s
 * @param {string[]} words
 * @return {number[]}
 */
var findSubstring = function (s, words) {
  // 滑动窗口题

  // 每个单词的长度
  const step = words[0].length
  // 返回结果
  const res = []

  if (s.length < step) return res

  // 获取所有需要的单词的个数
  const needs = {}
  for (const str of words) {
    needs[str] = (needs[str] || 0) + 1
  }

  // 为了处理 s 串中并非所有结果都和 words 保持对齐的情况，需要遍历 step 次
  for (let i = 0; i < step; i++) {
    // 存储窗口中的单词
    const window = {}
    // 已有的符合条件的单词个数
    let count = 0
    // 左右指针
    let left = i, right = i

    // 如果还没有遍历完 s 串，扩展窗口
    while (right < s.length) {
      // 获取要新加入窗口的单词
      const w = s.substring(right, right + step)
      // 扩展窗口
      right += step

      // 如果新加入窗口的单词是需要的单词
      if (needs[w]) {
        window[w] = (window[w] || 0) + 1
        // 如果新加入窗口单词的已记录个数和需要的个数相等
        if (window[w] === needs[w]) {
          count++
        }
      }

      // 如果窗口长度等于 words 的总宽度,缩小窗口
      while (right - left >= step * words.length) {
        // 找到了所有需要的单词
        if (count === Object.keys(needs).length) {
          res.push(left)
        }
        // 获取要移除窗口的单词
        const w = s.substring(left, left + step)
        // 缩小窗口
        left += step

        // 如果移除窗口的单词是需要的单词
        if (needs[w]) {
          // 如果移除窗口的单词的已记录个数和需要的个数相等
          if (window[w] === needs[w]) {
            count--
          }
          window[w]--
        }
      }
    }
  }

  return res
};

console.log(findSubstring("barfoothefoobarman", ["foo", "bar"])); // [0, 9]
console.log(findSubstring("wordgoodgoodgoodbestword", ["word", "good", "best", "word"])); // []
console.log(findSubstring("barfoofoobarthefoobarman", ["bar", "foo", "the"])); // [6, 9, 12]
console.log(findSubstring("wordgoodgoodgoodbestword", ["word", "good", "best", "good"])); // [8]
console.log(findSubstring("lingmindraboofooowingdingbarrwingmonkeypoundcake", ["fooo", "barr", "wing", "ding", "wing"])); // [13]
